<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
<script>
  {
    /**
     * 求数组 [1,2,3,4] 所有组合，例如[[1], [1,2], [1,2,3], [1,2,3,4], [2], [2,3]...]
     *
     * */
    const arr = [1, 2, 3, 4]
    const len = arr.length
    const rst = []
    const path = []

    function backtrack(start) {
      for (let i = start; i < len; i++) {
        path.push(arr[i])
        rst.push([...path])
        backtrack(i + 1)
        path.pop()
      }
    }

    backtrack(0)
    // console.log(rst)
  }
</script>
<script>
  {
    /**
     * 怎么做剪枝(优化掉不必要的循环)？
     * 只要求组合长度大于等于4的
     *
     * */
    const arr = [1, 2, 3, 4, 5]
    const len = arr.length
    const rst = []
    const path = []

    const limit = 4

    function backtrack (start) {

      for (let i = start;i < len; i ++) {
        // 优化
        if ((path.length + (len - i)) < limit) return

        path.push(arr[i])
        if (path.length >= limit) {
          rst.push([...path])
        }
        backtrack(i + 1)
        path.pop()
      }
    }
    backtrack(0)
    // console.log(rst)
  }
</script>
<script>
  {
    /**
     * 这是一道面试题
     *
     * 输入一个数组，给出这个数组中元素相加等于特定值的所有组合
     * 例如：[1, 2, 3, 4, 5, 6]，值相加等于7的组合：[1, 6]，[3, 4]，[2, 5]
     *
     * */

    function fn (subLen) {
      const rst = []
      const arr = [1, 2, 3, 4, 5, 6, 8]
      const len = arr.length
      const path = []
      let sum = 0

      function backtrack (start) {
        for (let i = start; i < len; i ++) {
          if (arr[i] > 7 || sum > 7) {
            // console.log('加前优化掉的',JSON.stringify(path))
            return
          }
          path.push(arr[i])
          sum = sum + arr[i]
          if (sum === 7 && path.length === subLen) {
            rst.push([...path])
          }
          if (sum > 7) {
            sum = sum - arr[i]
            // console.log('加后优化掉的',JSON.stringify(path))
            path.pop()
            return;
          }
          console.log('执行了',JSON.stringify(path))
          backtrack(i + 1)
          path.pop()
          sum = sum - arr[i]
        }
      }
      backtrack(0)

      return rst
    }
    // console.log(fn(2))
  }
</script>
</body>
</html>
